#include <string>
#include <iostream>
#include <vector>

namespace S1 {
    class Solution {
    public:
        std::string longestCommonPrefix(std::vector<std::string>& strs) {
            if (strs.size() <= 0) {
                return "";
            }
            
            std::string prefix = strs[0];
            std::string p;
            int index = 0;
            for(int i = prefix.size(); i > 0; i--) {
                p = prefix.substr(0, i);
                bool isEqual = true;
                for (int j = 1; j < strs.size(); j++) {
                    if (strs[j].compare(0, p.size(), p) != 0) {
                        isEqual = false;
                        break;
                    }
                }
                if (isEqual) {
                    return p;
                } else {
                    p = "";
                }
            }

            if (p.empty()) {
                return "";
            }
            return p;
        }
    };
}

namespace S2 {
    class Solution {
    public:
        std::string longestCommonPrefix(std::vector<std::string>& strs) {
            if (strs.empty()) {
                return "";
            }
            std::string prefix = strs[0];
            int count = strs.size();
            for (int i = 1; i < count; ++i) {
                prefix = longestCommonPrefix(prefix, strs[i]);
                if (!prefix.size()) {
                    break;
                }
            }
            return prefix;
        }

        std::string longestCommonPrefix(std::string str1, std::string str2) {
            int length = std::min(str1.size(), str2.size());
            int index = 0;
            while (index < length && str1[index] == str2[index]) {
                index ++;
            }
            return str1.substr(0, index);
        }
    };


}



int main() {
    std::vector<std::string> strs { "flower", "flow", "flight" };
    // std::vector<std::string> strs { "dog","racecar","car" };
    S2::Solution s1;
    auto pre = s1.longestCommonPrefix(strs);
    std::cout << pre << std::endl;
}